package com.zc.easy.No20;

import java.util.*;

/**
 * @program: leetCode_Exercise
 * @author: zhangcong
 * @create: 2019-09-18 11:41
 * @description: 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 * <p>
 * 示例 1:
 * 输入: '()'
 * 输出: true
 * <p>
 * 示例 2:
 * 输入: '()[]{}'
 * 输出: true
 * <p>
 * 示例 3:
 * 输入: '(]'
 * 输出: false
 * <p>
 * 示例 4:
 * 输入: '([)]'
 * 输出: false
 * <p>
 * 示例 5:
 * 输入: '{[]}'
 * 输出: true
 **/
public class Solution {
    public static boolean isValid(String s) {
        if(s.length()==0){
            return true;
        }
        if(s.length() % 2 > 0){
            return false;
        }
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        if (!map.containsKey(s.charAt(0))) {
            return false;
        }
        char[] charArray = s.toCharArray();
        List<Character> tempList=new ArrayList<>();
        for (int i = 0; i < charArray.length; i++) {
            char ch=charArray[i];
            //判断如果是左括号，加入list
            if(map.containsKey(ch)){
                tempList.add(ch);
            }else if(map.containsValue(ch)){
                //如果是右括号，必须与最近的左括号对应
                Character temp = tempList.get(tempList.size() - 1);
                if(!map.get(temp).equals(ch)){
                    return false;
                }else {
                    tempList.remove(tempList.size()-1);
                }
            }else {
                return false;
            }
        }
        if(tempList.size()>0){
            return false;
        }
        return true;
    }



    public static void main(String[] args) {
        String str="{[[]({[}})]}";
        System.out.println(String.valueOf(isValid(str)));
    }
}
